package com.darrenchan.leetcode;

import java.util.Stack;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-22 22:34
 */
public class Q114 {
    private TreeNode lastNode;

    //递归
    public void flatten(TreeNode root) {
        if(root == null) {
            return;
        }

        if(lastNode != null) {
            lastNode.left = null;
            lastNode.right = root;
        }

        lastNode = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }

    //非递归
//    public void flatten(TreeNode root) {
//        if(root == null){
//            return;
//        }
//
//        Stack<TreeNode> stack = new Stack<>();
//        stack.add(root);
//        while(!stack.isEmpty()){
//            root = stack.pop();
//            if(root.right != null){
//                stack.add(root.right);
//            }
//            if(root.left != null){
//                stack.add(root.left);
//            }
//
//            root.left = null;
//            if(!stack.isEmpty()){
//                root.right = stack.peek();
//            }
//        }
//    }
}
